模拟赛题解/2025.10.11 模拟赛

T1-那头与艺术（art）

题面

那头现在有 $n$ 种可以表演的行为艺术，第 $i$ 种有一个特征值 $a_i$（$a_i$ 可能相同）。那头在一轮表演中会按某个顺序表演每种艺术恰好一次。我们称一轮表演构成了序列 $s$，当且仅当在这一轮表演中那头表演的第 $i$ 项艺术的特征值为 $s_i$。那头认为如果两轮表演构成的序列分别为 $p,q$，那么就会产生 $LCS(p,q)$ 的不优美度。现在那头希望你给他指定两种表演顺序，他将按这两种顺序各表演一轮。但是为了凸显艺术性，他将在第二轮表演之前任意循环左移你给定的顺序。现在，你需要最小化这两轮表演可能产生的不优美度的最大值，并给出方案。

形式化题意：给定长为 $n$ 的序列 $a$，你需要构造 $a$ 的两个重排 $b$ 和 $c$，最小化 $\max_{i=0}^{n−1}LCS(b,f(c,i))$， 其中 $f(c,i)$ 表示序列 $c$ 循环左移 $i$ 位得到的序列。

注：$LCS(s,t)$ 表示序列 $s$ 和序列 $t$ 的最长公共子序列。

$1\leq n\leq 500,1\leq a_i\leq 10^9$。

题解

首先特判掉 $a$ 中所有元素相同的情况。

容易发现答案有一个下界：$a$ 中众数出现的次数加一。

具体的，记众数为 $A$，任意一个其他的数为 $B$。那么 $b,c$ 形如 $\dots A\dots A\dots B\dots A\dots A\dots A\dots$。显然可以通过循环移位使得 $b,c$ 中只包含 $A$ 和 $B$ 的子序列相等。 尝试构造取到这个下界。 一种构造方案是 $b$ 为 $a$ 升序排列后的结果，$c$ 通过不断降序取 $a$ 中剩余元素各一个得到。 例如：$a=\{1,3,2,4,2,3,4,4\}$ ，则构造 $b=\{1,2,2,3,3,4,4,4\},c=\{4,3,2,1,4,3,2,4,3,4\}$。容易发现上述构造符合要求。

T2-那头与追忆（recall）

题面

在那头的记忆中，他曾经写过如下的代码：

#define ll long long
ll a[1000005],cnt;
void solve(ll l,ll r)
{
	ll maxn=−1,id=0;
	for(ll i=l;i<=r;++i)
    {
        ++cnt;
        if(a[i]>maxn) maxn=a[i],id=i;
    }
	if(l<id) solve(l,id−1);
	if(id<r) solve(id+1,r);
}

现在那头给你一个长度为 $n$ 的排列 $a$，并 $q$ 次询问你，第 $i$ 次询问给出 $l_i,r_i$。你需要回答他，如果他将 $cnt$ 设为 $0$，然后调用 $solve(l_i,r_i)$ 之后 $cnt$ 的值是多少。

$1\leq n,q\leq10^6,1\leq l_i\leq r_i\leq n$。

题解

问题本质即为区间笛卡尔树所有子树 $size$ 和。 考虑算 $a_i$ 结点在整个序列的笛卡尔树 $size$ 大小，考虑找到 $i$ 左边第一个比他大的位置 $+1$,右边第一个比他大的位置 $-1$，分别记为 $l_i,r_i$，它的 $size$ 即为 $r_i-l_i+1$，加上每次询问区间的限制 $[ql,qr]$ 即为 $\sum_{i=ql}^{qr}(\min(qr,r_i)-max(ql,l_i)+1)$。

分别做 $min(qr,r_i),max(ql,l_i)$，这里以 $min(qr,r_i)$ 为例： 离线做扫描线，对于 $i$ 维护每个 $j$（$j\leq i$）此时的 $\min(i,l_j)$，按 $l_j$ 排序，在 $i>l_j$ 时单点修改即可。$max(ql,l_i)$ 是类似的。

时间复杂度 $O(n\log n)$。

T3-那头与星铁（starrail）

题面

那头有 $n$ 个头和 $m$ 条通信线路，每条通信线路双向连接了两个头，并且有一个权值。由于那头认为排列是可爱的，所以保证通信线路的权值构成了 $1\sim m$ 的一个排列。如果将那头的头和通信线路视为一张无向图 $G$，那么那头保证 $G$ 连通且没有重边和自环。那头定义一张无向图 $X$ 的关键森林 $f(X)$ 表示 $X$ 中每个连通块的最小生成树的并集。

为了游玩《崩坏·星穹铁道》，那头需要改变自己。具体地，那头现在想要改变这些通信线路的权值，又不想改动关键森林，于是他要求你计数满足以下条件的无向图 $G_0$ 的数量：

$G$ 与 $G_0$ 的点集与每条边所连接的点均相同，仅有边的权值不同，且对于边集的任意一个子集 $S$，设 $S$ 在 $G$ 中构成子图 $g$，在 $G_0$ 中构成子图 $g_0$，那么有 $f(g)=f(g_0)$。

那头很宽容，所以你只需要输出答案对 $998244353$ 取模的值。

$3\leq n,m\leq 5\times 10^5$。

题解

考虑 $G$ 合法的条件。有一个显然的充要条件是对于每个环，$G$ 中权值最大 的边与 $G$ 中权值最大的边相同。

尝试刻画边之间的大小限制。按边权从小到大加边，设当前加入的边为 $e$， 那么限制 $e$ 的边权大于加边后 $e$ 所在点双中的其他所有边。

实际上，对于每个点双，取这个点双最新出现的边作为代表边，那么如果在 $e$ 加入前 $u,v$ 位于同一点双中，只需要限制 $e$ 的边权大于这个点双的代表边。否则限制 $e$ 大于 $u$ 所在边双代表边和 $v$ 所在点双代表边。

发现上述限制关系构成一棵森林。我们需要求该森林的拓扑序个数。根据经典结论，设 $e$ 加边后 $e$ 所在点双大小为 $siz_e$，答案即为 $\frac{m!}{\prod siz_e}$。暴力实现上述做法复杂度 $O(n^2)$。

现在我们只需要动态加边维护点双。为了方便实现，可以先加入 G 的最小生成树上的所有边。动态维护圆方树，对于每个圆点 $u$，用并查集维护 $u$ 的父 亲（一个方点）。设当前加入的边为 $(u,v)$，如果 $LCA(u,v)$ 是一 个方点，则把路径上所有方点合并到 $LCA(u,v)$，否则合并到 $fa_{LCA(u,v)}$。 找到路径上的方点只需要不断跳 $u,v$ 中 $dep$ 较大的一个即可。

复杂度 $O(n\log n)$。

T4-那头与串串（string）

题面

现在那头输出了一个长度为 $n$，字符集 $P\in \{1,2,\cdots ,n\}$ 的字符串 $a$。由于你的 $\text{prompt}$ 限制，$a$ 中每个字符最多会出现两次。现在你需要求出 $a$ 的本质不同子串个数。

但是这也太板了！所以我们修改了一下本质不同子串的定义。定义子串 $a[l1,r1]$ 与 $a[l2,r2]$ 本质不同，当且仅当可重集 $S={a_{l_1} ,a_{l_1+1},\cdots,a_{r_1}}$ 不等于可重集 $T={a_{l_2},a_{l_2+1},\cdots,a_{r_2}}$。

$1\leq n\leq 5\times10^5,1\leq a_i\leq n$。

题解

记 $S[l,r]$ 表示可重集 $\{a_l,a_{l+1},\dots,a_r\}$。对于每个 $i$，记 $nxt_i$ 表示满足 $j>i,a_j=a_i$ 的 $j$，如果不存在则为 $-1$。

对于一个区间 $[l,r]$，如果存在区间 $[l',r']$ 满足 $S[l,r]=S[l',r']$ 且 $r<l$， 则这等价于 $r-l+1=r'-l+1$ 且 $\min_{i\in[l,r]}nxt_i=l',\max_{i\in[l,r]}nxt_i=r'$。这还意味着 $[l',r']$ 是唯一的满足 $S[l,r]=s[l',r']$ 的区间 $[l',r']$。

我们称 $[l',r']$ 是 $[l,r]$ 的关键区间。

考虑一个大于两个集合构成的等价类 $\{[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\}$。我们 钦定 $l_i<l_{i+1}$。容易发现这种情况只会发生在 $r_1\geq l_k$ 时。发现对于相交的 $[l,r]$ 与 $[l',r']$（$l\leq l'$），$S[l,r]=S[l',r']$ 当且仅当 $[r+1,r']$ 是 $[l,l'-1]$ 的关键区间。

我们希望对于 $[l_i,r_i]$ 只减去 $[l_{i+1},r_{i+1}]$ 的贡献方便统计。考虑如下算法：先默认答案为 $\frac{n\times(n+1)}2$，枚举 $l$，增加 $r$，如果存在 $[l',r']$ 且 $l'=r+1$，则将 答案减一；如果 $l'$ 对于这个 $l$ 首次出现，则将答案额外减一。容易发现上述 算法的正确性。直接实现复杂度小常数 $O(n^2)$。

尝试加速统计。从右到左扫描 $l$，对于每个 $r$，维护 $mn_r,mx_r$ 表示 $\min_{i\in[l,r]}nxt_i$ 和 $\max_{i\in[l,r]}nxt_i-\min_{i\in[l,r]}nxt_i-(r-l)$。这可以通过一个经典的单调栈技巧实现（通过单调栈将 $cmax,cmin$ 操作转为区间加减）。

需要统计所有 $sum_r=0$ 的位置以及满足 $sum_r$ 的位置中 $mn_r$ 出现的种数。由于 $sum_r\geq0$，所以统计 $sum_r=0$ 的个数只需要记录 $sum_r$ 的最小值以及最小值的个数。由于 $mn_r$ 不增，种数即为颜色段数。这些信息都是容易合并的，直接用线段树维护即可，复杂度 $O(n\log n)$。